📋 Task Scheduling with Min Heap

Prioritize tasks efficiently — filter based on root priority threshold.

📋 Emma's Task Scheduling Challenge

🎯 The Challenge:

Emma needs to build a task scheduling system that filters tasks based on a priority threshold derived from the most urgent task.

📋 Requirements:

  • Build a Min Heap from task priorities
  • Find the root (minimum priority task)
  • Calculate threshold = 2 × root priority
  • Remove all tasks with priority < threshold
  • Display remaining tasks in level-order (heap array)

Problem Specifications

  • Input: n (1 ≤ n ≤ 20), followed by n priorities (1 ≤ priority ≤ 1000)
  • Process: Build Min Heap → Calculate threshold → Filter → Maintain heap property
  • Output: Remaining tasks in level-order (space-separated)

Example: n = 7, priorities = [4, 8, 6, 15, 12, 10, 14]

Step 1 - Build Min Heap:
4 8 6 15 12 10 14
Root = 4, Threshold = 2 × 4 = 8
Remove all tasks with priority < 8
Step 2 - After Filtering:
4 8 6 15 12 10 14
Step 3 - Rebuild Heap & Output:
8 10 12 15 14

🔄 Min Heap Filtering Strategy

Algorithm Steps

  1. Build a Min Heap from input priorities
  2. Identify the root element (minimum priority)
  3. Calculate threshold = 2 × root priority
  4. Filter: Keep only tasks with priority ≥ threshold
  5. Rebuild Min Heap from remaining tasks
  6. Output heap in level-order traversal (array representation)

Key Insight: After filtering, we must rebuild the heap to maintain the min heap property.

Building Min Heap

Time: O(n log n)
Insert n elements into heap

Filtering & Rebuild

Time: O(k log k)
k = remaining tasks after filter

Why Rebuild the Heap?

Simply removing elements from the heap array would break the heap property. We need to:

  • Collect all elements that meet the threshold criteria
  • Build a fresh Min Heap from these elements
  • This ensures parent ≤ children relationship is maintained

🔍 Step-by-Step Task Filtering Demo

Ready. Use controls below to start demo.

Min Heap State

Remaining Tasks After Filtering

Not yet processed
Click Start to run demo

Progress Tracker

1. Parse input priorities
2. Build Min Heap
3. Get root and calculate threshold
4. Filter tasks based on threshold
5. Rebuild Min Heap from remaining
6. Output level-order traversal

🎮 Build Your Task Scheduler

Enter data and press Process Tasks

Test Cases

Sample Input
n = 7
Priorities: 4 8 6 15 12 10 14
Expected: 8 10 12 15 14
Small Test
n = 3
Priorities: 10 20 15
Try it yourself!
Another Example
n = 5
Priorities: 5 10 3 8 12
Root=3, Threshold=6

📊 Analysis & Optimization

Time

O(n log n)

Building heap dominates complexity

Space

O(n)

Storing task priorities

Detailed Complexity Breakdown

  • Building Initial Heap: O(n log n) - inserting n elements
  • Finding Root: O(1) - always at index 0
  • Filtering: O(n) - linear scan through heap array
  • Rebuilding Heap: O(k log k) where k ≤ n
  • Overall: O(n log n)

Key Implementation Points

  • Min Heap uses array representation: parent at i, children at 2i+1 and 2i+2
  • After filtering, must rebuild heap to maintain property
  • Level-order traversal is simply the heap array
  • Threshold comparison: keep tasks with priority ≥ 2 × root

Real-World Applications

  • Task scheduling in operating systems
  • Priority-based job queues
  • Event-driven simulations
  • Resource allocation systems